//
// Created by liuwenwen on 12/17/2019.
//


#include <iostream>
#include <iomanip>

using namespace std;

//哈夫曼树的存储表示
typedef struct
{
    int weight;    // 权值
    int parent;    // 父节点
    int lChild;    // 左孩子下标
    int rChild;    // 右孩子下标
} HTNode, *HuffmanTree;


// 选择权值最小的两颗树
void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)
{
    s1 = s2 = 0;

    int i;
    for (i = 1; i < n; ++i)
    {
        if (0 == hT[i].parent)
        {
            if (0 == s1)
            {
                s1 = i;
            } else
            {
                s2 = i;
                break;
            }
        }
    }
    if (hT[s1].weight > hT[s2].weight)
    {
        int t = s1;
        s1 = s2;
        s2 = t;
    }

    for (i += 1; i < n; ++i)
    {
        if (0 == hT[i].parent)
        {
            if (hT[i].weight < hT[s1].weight)
            {
                s2 = s1;
                s1 = i;
            } else if (hT[i].weight < hT[s2].weight)
            {
                s2 = i;
            }
        }
    }
}

// 构造有n个权值（叶子节点）的哈夫曼树
void CreateHuffmanTree(HuffmanTree &hT)
{
    int n, m;       // n代表叶子节点个数，m代表总节点个数
    cin >> n;       // 输入叶子节点个数
    m = 2 * n - 1;        // 2n-1=n+n-1，n-1是因为n0=n2+1

    hT = new HTNode[m + 1];    // 0号节点不使用，用于保存节点数量
    for (int i = 1; i <= m; ++i)
    {
        hT[i].parent = hT[i].lChild = hT[i].rChild = 0;     // 各个数据初始化为0
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> hT[i].weight;    // 输入权值
    }
    hT[0].weight = m;    // 用0号节点保存节点数量

    /****** 初始化完毕, 创建哈夫曼树 ******/
    for (int i = n + 1; i <= m; ++i)        // 从非叶子节点处开始遍历
    {
        int s1, s2;     // 定义两个节点的下标
        SelectMin(hT, i, s1, s2);       // 选择权值最小的两棵树

        hT[s1].parent = hT[s2].parent = i;      //
        hT[i].lChild = s1;    // 作为新节点的孩子
        hT[i].rChild = s2;    // 作为新节点的孩子
        hT[i].weight = hT[s1].weight + hT[s2].weight;    // 新节点为左右孩子节点权值之和
    }
}


// 计算WPL（供仅传参树的跟节点的函数调用）
int HuffmanTreeWPL(HuffmanTree hT, int i, int depth)
{
    if (hT[i].lChild == 0 && hT[i].rChild == 0)
    {
        return hT[i].weight * depth;
    }
    else
    {
        return HuffmanTreeWPL(hT, hT[i].lChild, depth + 1) + HuffmanTreeWPL(hT, hT[i].rChild, depth + 1);
    }
}

// 计算WPL（带权路径长度）
int HuffmanTreeWPL(HuffmanTree hT)
{
    return HuffmanTreeWPL(hT, hT[0].weight, 0);
}

// 输出哈夫曼树各节点的状态
void Print(HuffmanTree hT)
{
    cout << "index weight parent lChild rChild" << endl;
    cout << left;    // 左对齐输出
    for (int i = 1, m = hT[0].weight; i <= m; ++i)
    {
        cout << setw(5) << i << " ";
        cout << setw(6) << hT[i].weight << " ";
        cout << setw(6) << hT[i].parent << " ";
        cout << setw(6) << hT[i].lChild << " ";
        cout << setw(6) << hT[i].rChild << endl;
    }
}

// 销毁哈夫曼树
void DestroyHuffmanTree(HuffmanTree &hT)
{
    delete[] hT;        // 释放数组hT的内存空间
    hT = nullptr;       // 将hT的指针置为空
}

int main()
{
    HuffmanTree hT;
    CreateHuffmanTree(hT);
    Print(hT);
    cout << "WPL = " << HuffmanTreeWPL(hT) << endl;
    DestroyHuffmanTree(hT);
    return 0;
}